package org.czl.leetcode4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class l2608 {
    public static void main(String[] args) {
        //[1,3],[3,5],[5,7],[7,1],[0,2],[2,4],[4,0],[6,0],[6,1]
        System.out.println(findShortestCycle(8, new int[][]{{1, 3}, {3, 5}, {5, 7}, {7, 1}, {0, 2}, {2, 4}, {6, 0},{6,1}}));
    }
    //并查集加bfs
    static int[] father;
    static int[] size;
    static int find(int x){
        if(father[x] != x){
            father[x] = find(father[x]);
        }
        return father[x];
    }
    static void union(int x, int y){
        int fx = find(x);
        int fy = find(y);
        if(fx != fy){
            father[fx] = fy;
            size[fy] += size[fx];
        }
    }
    static boolean isSame(int x, int y){
        return find(x) == find(y);
    }
    static int getSize(int x){
        return size[find(x)];
    }
    public static int findShortestCycle(int n, int[][] edges) {
        int m = edges.length;
        //建图
        father = new int[n];
        size = new int[n];
        List<Integer>[] edge = new ArrayList[n];
        for(int i = 0; i < n; i++){
            father[i] = i;
            size[i] = 1;
            edge[i] = new ArrayList<>();
        }

        for(int i = 0; i < m; i++){
            int x = edges[i][0];
            int y = edges[i][1];
            edge[x].add(y);
            edge[y].add(x);
        }
        int ans = Integer.MAX_VALUE;
        int[] stack = new int[2001];
        int index = 0;
        for(int i = 0; i < n; i++){
            if(i != father[i])continue;

            List<Integer> to = edge[i];
            if(to.size()!= 2){
                continue;
            }
            stack[index++] = i;
            while(index != 0){
                int no = stack[--index];
                List<Integer> node = edge[no];
                if(node.size() != 2){
                    index = 0;
                    break;
                }
                int left = node.get(0);
                int right = node.get(1);
                if(!isSame(left, no)){
                    union(left, no);
                    stack[index++] = left;
                }
                if(!isSame(right, no)){
                    union(right, no);
                    stack[index++] = right;
                }
                if(edge[left].size() != 2 || edge[right].size() != 2){
                    index = 0;
                    break;
                }
                if(isSame(no, left) && isSame(no, right)){
                    ans = Math.max(ans, getSize(no));
                }
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
